package leetcode;

public class _0143 {
    /**
     * 重排链表
     */
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        private class ListNode {
            ListNode next;
            int val;
            ListNode(){}
            ListNode(int val){
                this.val=val;
            }
            ListNode(int val, ListNode next){
                this.val = val;
                this.next = next;
            }
        }
        public void reorderList(ListNode head) {
            ListNode mid = middleNode(head);
            ListNode head2 =reverseList(mid);
            while(head2.next!=null){
                ListNode nxt1 = head.next;
                ListNode nxt2 = head2.next;
                head.next = head2;
                head2.next = nxt1;
                head = nxt1;
                head2 = nxt2;
            }
        }
        public ListNode middleNode(ListNode head){
            ListNode slow = head, fast = head;
            while(fast!=null&&fast.next!=null){
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
        public ListNode reverseList(ListNode head){
            ListNode pre = null,cur = head;
            while(cur!=null){
                ListNode nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            return pre;
        }
    }
}
